#include <pthread.h>
#include <iostream>
#include <fstream>
using namespace std;

// g++ -pthread

/* Ilość wierzcholkow. */
int N;
/* Ilość krawedzi. */
int M;

/* Dlugosci krawedzi. */
int **G;
/* Wartosci najkrotszycj sciezek. */
int **g;

/* 
 * Macierz kierowana ruchem. 
 * Prechowuje optymalne wartosci posrednich wierzcholkow.
 */
int **R;

/* 
 * Stała służąca za wartość nieskończoną. 
 * Z jakiegos powodu niedzala macro z <climits>
 */
const int INF = 10001;

void 	konstruktor	(void);
void	destruktor	(void);
void	wczytywanie	(fstream &plik);
void	droga		(int u, int v);

void	*setup_G	(void* unused);
void	*setup_g	(void* unused);
void	*setup_R	(void* unused);
void	*setup_0	(void* unused);
void	*floyd1		(void* unused);
void	*floyd2		(void* unused);


int main(){
    pthread_t thread1_id;
    pthread_t thread2_id;
    pthread_t thread3_id;
    pthread_t thread4_id;
    
    fstream plik;
    plik.open("dane.txt");
    ios_base::sync_with_stdio(0);
    plik >> N >> M;
	konstruktor();

	pthread_create( &thread1_id, NULL, &setup_G, NULL);
	pthread_create( &thread2_id, NULL, &setup_g, NULL);
	pthread_create( &thread3_id, NULL, &setup_R, NULL);
	pthread_create( &thread4_id, NULL, &setup_0, NULL);
      
	pthread_join( thread1_id, NULL);
	pthread_join( thread2_id, NULL);
	pthread_join( thread3_id, NULL);
	pthread_join( thread4_id, NULL);

	wczytywanie(plik);    
    plik.close();
	pthread_create( &thread1_id, NULL, &floyd1, NULL);
	pthread_create( &thread2_id, NULL, &floyd2, NULL);

	int a1,a2;
	cin >> a1 >> a2;
	pthread_join(thread1_id, NULL);
	cout << a1 << " -> " << a2 << " : " << g[a1-1][a2-1] << endl << a1 <<" ";
	droga(a1-1,a2-1);
	cout << a2 << endl;

	destruktor();
    return 0;
}

//-----------------------------
void konstruktor (void) {
	G = new int*[N];
	g = new int*[N];
	R = new int*[N];
	for(int i=0; i<N; ++i)
	{
		G[i] = new int[N];
		g[i] = new int[N];
		R[i] = new int[N];
	}
}
//-----------------------------
void destruktor (void) {
	for(int i=0; i<N; ++i)
	{
		delete [] R[i];
		delete [] g[i];
		delete [] G[i];
	}
	delete [] R;
	delete [] g;
	delete [] G;
}
//-----------------------------
void droga(int u, int v) {
	if( R[u][v] != -1 ) {
		droga(u, R[u][v]);
		cout << R[u][v] + 1 <<" ";
		droga(R[u][v], v);
	}
}
//-----------------------------
void wczytywanie(fstream &plik) {
	int u, v, w;
	for(int i=0; i<M; ++i) {
		plik >> u >> v >> w;
		G[u-1][v-1] = g[u-1][v-1] = w;
    }
}
//-----------------------------
void *setup_G(void* unused) {
     for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
			if( i != j)	G[i][j] = INF;
    pthread_exit(NULL);
}
//-----------------------------
void *setup_g(void* unused) {
     for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
			if( i != j)	g[i][j] = INF;
    pthread_exit(NULL);
}
//-----------------------------
void *setup_R(void* unused) {
	for(int i=0; i<N; ++i)
		for(int j=0; j<N; ++j)
			R[i][j] = -1;
    pthread_exit(NULL);
}
//-----------------------------
void *setup_0(void* unused) {
	for(int i=0; i<N; ++i)
	{
		G[i][i] = 0;
		g[i][i] = 0;
	}
    pthread_exit(NULL);
}
//-----------------------------
void *floyd1(void* unused) {
    for(int k=0; k<(N/2); ++k)
        for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
                if( g[i][j] > g[i][k] + g[k][j] )
				{
					g[i][j] = g[i][k] + g[k][j];
					R[i][j] = k;
                }
    pthread_exit(NULL);
}
//-----------------------------
void *floyd2(void* unused) {
    for(int k=(N/2)+1; k<N; ++k)
        for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
                if( g[i][j] > g[i][k] + g[k][j] )
				{
					g[i][j] = g[i][k] + g[k][j];
					R[i][j] = k;
                }
    pthread_exit(NULL);
}
//-----------------------------
